The present invention is directed to compiling computer programs. It particularly concerns arrangements for compiling in one machine programs to be executed by another.
As is well known, a computer typically operates by fetching the contents of a memory location that a program counter specifies and then interpreting the binary code thus fetched as a machine-language instruction. The instruction always includes an operation code, i.e., a binary number that represents one of the repertoire of atomic operations of which that particular microprocessor is capable. One such atomic operation, for instance, is the addition of two integer operands. The instruction may additionally include codes for locations from which the operation's operands are to be drawn and the destination in which the operation's result is to be stored. So a single instruction may specify, for instance, that the microprocessor's arithmetic logic unit is to add the contents of microprocessor registers A and B and place the results in microprocessor register C.
As is also well known, manually programming a computer at this level is extremely time-consuming and error-prone. So compilers were early developed to write such machine code in response to higher-level instructions, which the programmer supplies. A compiler enables the human user to employ language that is much easier to understand than the numerical codes to which the microprocessor responds. Also, it usually takes much fewer compiler-language instructions than machine-language instructions to define a given procedure. Some compilers additionally check for lapses in consistency, alerting the programmer when, say, the program as written would add a string to an integer. And the compiler language employed by a human programmer can be independent of the particular microprocessor type that ultimately will execute the computer-generated machine code; the compiler can concern itself with the type of machine on which the code is to execute and relieve the human programmer of the need to be aware of different microprocessors' peculiarities.
A further advantage of many high-performance compilers is that they optimize the resultant machine code to some extent. A computer program can be thought of as a function that responds to inputs by generating outputs. It is ordinarily true that more than one set of steps is available that can produce an output having the desired relationship to the input, and it usually is also true that the amounts of time or other resources required to perform the different sets of steps differ widely. So many compilers have been provided with the intelligence to select one of the equivalent-output sets of atomic-step sequences that are relatively inexpensive in time or some other system resource.
A compiler that can perform all of these functions can be time- and resource-consuming in operation. So the compilation operation should be performed only once, if possible, rather than every time the resultant program is executed. Of course, this ideal cannot always be achieved; a given program may sometimes be run on more than one machine, and, because of the different machines' instruction repertoires and other features, different machine code will have to be produced from the same source (compiler) code. This ordinarily requires that different versions of the same compiler to produce machine code for the different executing machines.
A partial exception to this model of performing different compilations for different machines has resulted from the popular adoption of internetworking, in which millions of computer nodes are loosely interconnected in such a manner that communications occur between parties who are acquainted neither with each other nor with their respective types of computer equipment. This reality has given rise to the use of virtual-machine code. By far the most popular way to generate such code is to use a compiler that generates machine code from source code written in the Java.TM.-programming language. (Sun, the Sun Logo, Sun Microsystem, and Java are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. All SPARC trademarks are used under license and are trademarks of SPARC International, Inc. in the United States and other countries. Products bearing SPARC trademarks are based upon an architecture developed by Sun Microsystems, Inc.) But the teachings of this invention described below are equally applicable to virtual-machine code generated from other-language source code.
A microprocessor used in implementing the machine code thus written does not ordinarily execute it directly: its program counter does not point to locations that contain the compiler-generated machine code. Instead, it emulates a "virtual machine" for which that code is written. The compiler can perform all of the expensive analysis required for optimized translation from high-level constructs to low-level atomic operations, and the resultant "byte code," as such virtual-machine code is typically called, can be sent to different users employing different machines. All they need is some relatively simple run-time code that enables their particular machines to emulate the virtual machine for which this byte code is intended.
To appreciate this approach's benefits, consider FIG. 1. Through various interface circuitry not shown, a user at a location 12 may employ a keyboard 14 and display 16 to enter compiler-language ("source") code into, say, a read/write memory 18. For the sake of concreteness, FIG. 2 sets forth a five-line fragment exemplifying such source code. The first line declares three variables area, volume, and height as integers. It also sets the initial values of area and height to zero. The second line specifies that the sequence of operations beginning with that line's opening brace and ending with the closing brace three lines later is to be repeated once for each value of height from 0 to 10,000,000-1. The third line, which is part of that sequence, indicates that area is to be incremented by the product of two values length and width. The fourth line states that volume is to be incremented by the product of length, width, and volume on every pass through that sequence. We assume for the sake of this example that the length and width variables have previously been declared integers and initialized to non-zero values.
A compiler program (in the form of machine code) is also loaded into memory 18 from, say, a disk drive 20. In accordance with that compiler program's machine-code instructions, a microprocessor 22 acts as a compiler, treating the user-entered compiler-language code as the compiler's input data and generating byte code as the compiler's output. A typical result of this operation would be byte code such as that which FIG. 3 represents mnemonically (i.e., in assembly language).
The first byte (byte 0) of that code represents "pushing" a zero-value integer onto a common operand stack associated with the method of whose definition the code fragment is a part. The next byte (byte 1) represents "popping" the operand stack's contents and storing them in local variable 2, one of a number of local variables associated with the method that the code implements. The machine code employs local variable 2 to contain the area value.
Bytes 2 through 6 represent similarly initializing the volume and height values. (The machine code requires only a single byte to specify that the top operand-stack value is to be stored in local variables 0, 1, 2, or 3. The underscore in, e.g. "istore.sub.-- 2" indicates that the local-variable reference is part of the same byte as the operation code. Instructions to store values in other variables use the generic integer-storage-operation code "istore." This code calls for an operation that pops the operand stack and stores the results in the local variable that the next byte specifies. So FIG. 3's line designated by off-set index 5 actually represents two bytes, and this is why the line after that bears offset index 7 rather than 6.)
The next six instructions best illustrate the virtual machine's stack-oriented nature. Bytes 10 through 12 contain operation codes that successively push the area, length, and width values onto the common operand stack. Byte 13 is simply an operation code for integer multiplication; it specifies no source or destination for the operands or result. This is characteristic of a stack-oriented machine: the source and destination for such machines' arithmetic operations are implicitly the common operand stack. As the line containing the byte-13 instruction indicates, that operation pops the operand stack's two top values, length and width, and pushes their product back onto the stack. The byte-14 instruction, whose operand code represents integer addition, similarly specifies that the operands are the top two stack values and that the result should be pushed back unto the stack. As the lines containing byte 15's instruction indicate, the next, "istore.sub.-- 2" instruction pops that result from the stack and stores it in the area-containing local variable 2.
A similar analysis of bytes 16 through 22 reveals that they update volume in accordance with the source program's directions and store the result in local variable 3. Bytes 25-28 represent incrementing the height variable, while bytes 30 and 32 represent branching to byte 10 if height has not yet reached the value, namely, 10,000,000, contained in the first entry of a constant pool included in the file that contains the byte code.
The resultant byte code will to be stored on the user's disk drive 20 or, say, on that of some other machine that acts as a "Web server." Such a machine responds to requests received by way of an internetwork, which FIG. 1 depicts in the customary manner as a cloud 28.
At a different location 30, a remote user, whose computer system 32 typically differs in many respects from the original programmer's system 34, receives from system 34 the file that contains the byte code produced at location 12. The computer systems and internetwork use electrical, electromagnetic, or optical signals that carry digital data streams. The signals that carry the digital data by which the computer systems exchange data are exemplary forms of carrier waves transporting the information.
When system 32 receives the byte code, it recognizes it as input to its virtual-machine-implementing program, such as the Java Runtime Environment. System 32's virtual-machine-implementing program accordingly produces the virtual machine's intended response to that byte code.
This approach has two principal advantages to the user at location 30. The first is that, even though the microprocessor that his system 32 employs is not necessarily of the same type as that used to compiled the code initially, he does not need to suffer the time cost that a full compilation of the source code for his own machine would necessitate; all that is necessary is the low-level conversion from the virtual machine's atomic operations to those of his own actual microprocessor.
The second is that the user at location 30 does not need to know or trust the virtual-machine code's source. If the remote source had instead compiled actual machine code that could run specifically on the microprocessor in system 32, there could be untoward consequences if the source by error or design included features that, say, adversely affect system 32's file system. In contrast, since the actual machine code that system 32's microprocessor executes is that of its own virtual-machine-implementing program or, at least, code that such a program has itself produced from the byte code, system 32's user needs only to trust his own virtual-machine software. Of course, the virtual-machine software is simulating a virtual-machine's response to code produced by a source not necessarily trusted, but the virtual-machine software can be (and, in the case of the Java Runtime Environment, actually is) so arranged as to prevent potentially destructive execution behavior, such as reading data locations' contents as instructions.
If the compilation operation's target is the virtual machine, it conventionally omits one feature found in conventional compilers. Specifically, the compiler that generates the virtual-machine code does not perform optimization that is specific to the actual machine on which the program will be run. Since different machines have different operation repertoires, register organizations, and so forth, a compiler targeted to a particular microprocessor can obtain an increment of performance for that processor that generic compilation does not conventionally afford. If the source compiler is not so targeted, the remote user's virtual-machine-implementation software, which is necessarily targeted to a specific actual machine, can perform a degree of optimization at its end. But the complexity of certain types of optimization, such as global register allocation by graph coloring, increases faster than linearly with the number of instructions in the code block being optimized, and the performance cost of having the run-time system perform such optimization can be unacceptable unless it is kept to a minimum. So the amount of machine-specific optimization that such systems perform is ordinarily quite limited.